﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0025_IsValidBST : IAlgorithm
    {
        // 验证二叉搜索树

        // 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

        // 有效二叉搜索树定义如下：
        //  节点的左子树只包含 小于 当前节点的数。
        //  节点的右子树只包含 大于 当前节点的数。
        //  所有左子树和右子树自身必须也是二叉搜索树。

        // 提示：
        //  树中节点数目范围在[1, 10^4] 内
        //  -2^31 <= Node.val <= 2^31 - 1

        public void Test()
        {
            var tree = new TreeNode(2)
            {
                left = new TreeNode(1),
                right = new TreeNode(3)
            };
            Console.WriteLine(IsValidBST(tree));
        }

        // 递归，注意条件需要左子节点不光要小于当前节点，还要大于父节点（右节点同理）
        public bool IsValidBST(TreeNode root)
        {
            return IsValidBST(root, long.MinValue, long.MaxValue);
        }
        public bool IsValidBST(TreeNode root, long minVal, long maxVal)
        {
            if (root == null)
                return true;
            //每个节点如果超过这个范围，直接返回false
            if (root.val >= maxVal || root.val <= minVal)
                return false;
            //这里再分别以左右两个子节点分别判断，
            //左子树范围的最小值是minVal，最大值是当前节点的值，也就是root的值，因为左子树的值要比当前节点小
            //右子数范围的最大值是maxVal，最小值是当前节点的值，也就是root的值，因为右子树的值要比当前节点大
            return IsValidBST(root.left, minVal, root.val) && IsValidBST(root.right, root.val, maxVal);
        }

        //中序遍历递归
        TreeNode prev;
        public bool IsValidBST1(TreeNode root)
        {
            if (root == null)
                return true;
            //访问左子树
            if (!IsValidBST1(root.left))
                return false;
            //访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。
            if (prev != null && prev.val >= root.val)
                return false;
            prev = root;
            //访问右子树
            if (!IsValidBST1(root.right))
                return false;
            return true;
        }

        //中序遍历非递归
        public bool IsValidBST2(TreeNode root)
        {
            if (root == null)
                return true;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode pre = null;
            while (root != null || stack.Count<=0)
            {
                while (root != null)
                {
                    stack.Push(root);
                    root = root.left;
                }
                root = stack.Pop();
                if (pre != null && root.val <= pre.val)
                    return false;
                //保存前一个访问的结点
                pre = root;
                root = root.right;
            }
            return true;
        }

    }
}
